package com.cyy.test_t_5_;

/**
 * @Description 剑指Offer t_58 - 二叉树的下一个结点
 * * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
 * * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 * @Author Crystal
 * @Date 2019/7/14 7:07
 * @Version 1.0
 **/
public class t_58 {
    /**
     * 定义二叉树
     */
    private static class TreeLinkNode {
        private int val;
        private TreeLinkNode left;
        private TreeLinkNode right;
        private TreeLinkNode parent;

        public TreeLinkNode() {
        }

        public TreeLinkNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }
    }

    public static TreeLinkNode GetNext(TreeLinkNode pNode) {
        /**
         * 思路分析：
         * 中序遍历：左->根->右
         * 根据二叉树特点，可分为两大类：
         * 1.有右子树的，那么下个结点就是右子树最左边的结点；
         * 2.没有右子树的，又可分为两类：
         *  2.1 是父节点的左孩子，那么父节点就是下一个结点
         *  2.2 是父节点的右孩子，那么向上找到它父节点的父节点。。。直到当前父节点是左孩子位置，
         *  如果没有，那么它就是尾节点。
         */

        if (pNode == null) return null;
        // 保存要查找的下一个节点
        TreeLinkNode target = null;

        if (pNode.right != null) {
            target = pNode.right;
            while (target.left != null) {
                target = target.left;
            }
            return target;
        } else if (pNode.parent != null) {
            target = pNode.parent;
            TreeLinkNode cur = pNode;
            // 如果父新结点不为空，并且，子节点不是父节点的左孩子
            while (target != null && target.left != cur) {
                cur = target;
                target = target.parent;
            }
            return target;
        }
        return null;
    }

    private static void assemble(TreeLinkNode node,
                                 TreeLinkNode left,
                                 TreeLinkNode right,
                                 TreeLinkNode parent) {
        node.left = left;
        node.right = right;
        node.parent = parent;
    }

    public static void main(String[] args) {
        test01();
    }

    //                            1
    //                  2                   3
    //             4         5          6          7
    //          8     9   10   11   12   13    14   15
    public static void test01() {
        TreeLinkNode n1 = new TreeLinkNode(1); // 12
        TreeLinkNode n2 = new TreeLinkNode(2); // 10
        TreeLinkNode n3 = new TreeLinkNode(3); // 14
        TreeLinkNode n4 = new TreeLinkNode(4); // 9
        TreeLinkNode n5 = new TreeLinkNode(5); // 11
        TreeLinkNode n6 = new TreeLinkNode(6); // 13
        TreeLinkNode n7 = new TreeLinkNode(7); // 15
        TreeLinkNode n8 = new TreeLinkNode(8); // 4
        TreeLinkNode n9 = new TreeLinkNode(9); // 2
        TreeLinkNode n10 = new TreeLinkNode(10); // 5
        TreeLinkNode n11 = new TreeLinkNode(11); // 1
        TreeLinkNode n12 = new TreeLinkNode(12); // 6
        TreeLinkNode n13 = new TreeLinkNode(13); // 3
        TreeLinkNode n14 = new TreeLinkNode(14); // 7
        TreeLinkNode n15 = new TreeLinkNode(15); // null

        assemble(n1, n2, n3, null);
        assemble(n2, n4, n5, n1);
        assemble(n3, n6, n7, n1);
        assemble(n4, n8, n9, n2);
        assemble(n5, n10, n11, n2);
        assemble(n6, n12, n13, n3);
        assemble(n7, n14, n15, n3);
        assemble(n8, null, null, n4);
        assemble(n9, null, null, n4);
        assemble(n10, null, null, n5);
        assemble(n11, null, null, n5);
        assemble(n12, null, null, n6);
        assemble(n13, null, null, n6);
        assemble(n14, null, null, n7);
        assemble(n15, null, null, n7);

        System.out.println(GetNext(n1));
        System.out.println(GetNext(n2));
        System.out.println(GetNext(n3));
        System.out.println(GetNext(n4));
        System.out.println(GetNext(n5));
        System.out.println(GetNext(n6));
        System.out.println(GetNext(n7));
        System.out.println(GetNext(n8));
        System.out.println(GetNext(n9));
        System.out.println(GetNext(n10));
        System.out.println(GetNext(n11));
        System.out.println(GetNext(n12));
        System.out.println(GetNext(n13));
        System.out.println(GetNext(n14));
        System.out.println(GetNext(n15));
    }
}